<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 初始化一个二叉树节点
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        // a是根节点
        var a = new TreeNode(3);
        var b = new TreeNode(0);
        var c = new TreeNode(2);
        var f = new TreeNode(4);
        var g = new TreeNode(1);
        var h = new TreeNode(5);
        a.left = b;
        a.right = f;
        b.right = c;
        c.left = g;
        f.left = h

        // 时间：O(n) 最多访问每个节点一次
        // 空间: O(n) 栈的使用情况可能和节点的个数一样大

        // 读题：
        // 1. 给定最小边界 low 和最大 high
        // 2. 修剪节点的值 [low, high] => 所有的值 都在这个区间
        // 3. 不改变保留在树中的元素的相对结构，只要没有被移除
        // 4. 有唯一的答案
        // 5. 返回根节点
        // 6. 每个节点的值都是唯一的


        // 算法：
        var trimBST = function (root, low, high) {
            debugger
            // 1. 判断root是否为空 返回null
            if (root === null) {
                return null
            }
            // 2. 判断当前节点值是否小于 low 是 =》递归右节点 进行返回
            // 为什么？
            // 因为如果当前节点值小于low 但是右节点 > 当前节点的值
            // 所以是有可能在区间范围内的，因此我们去递归遍历右节点
            if (root.val < low) {
                let right = trimBST(root.right, low, high)
                return right
            }
            // 3. 判断当前节点的值是否大于 low 是 =》递归左节点 返回左节点
            // 为什么？
            // 因为如果当前节点值大于high 但是左节点小于 当前节点的值
            // 所以是有可能在区间范围内的，因此我们去递归遍历左节点
            if (root.val > high) {
                let left = trimBST(root.left, low, high)
                return left
            }
            // 4. 然后还是要继续往下去遍历
            root.left = trimBST(root.left, low, high)
            root.right = trimBST(root.right, low, high)
            return root
        };
        // console.log(deleteNode(a, 8));
        console.log(trimBST(a, 1, 3));
    </script>
</body>

</html>